class Solution
{
public:
  int countNumbersWithUniqueDigits(int n)
  {
    // 如果【0位】只有【0一个】
    if (n == 0)
      return 1;

    // 如果【1位】就只有【0 ~ 9】10 个数
    if (n == 1)
      return 10;

    // 1. dp[i] 表示【i位】出现【不同数字】整数的【总个数】
    // - dp[i] 默认为 1
    // - 至少 存在【1个】不同数字的整数
    vector<int> dp(n + 1, 1);

    // 2. 赋值【有限位】对应的 dp[i] 值
    dp[0] = 1;
    dp[1] = 9;

    // 3. 先累加得到【0位】和【1位】出现不同数字整数的总个数【之和】
    int sum = dp[0] + dp[1];

    // 4. 计算从【2位】开始的不同数字整数的总个数【之和】
    for (int i = 2; i <= min(n, 10); i++) // min(n, 10) ==> 题目要求 n 最大为 10
    {
      /**
       *  dp[i-1] 已经用掉 i-1 个数
       *  那么 dp[i] 就只能从剩下 10-(i-1) ==> 11-i 个数中，选择【未使用】过的数字
       */
      dp[i] = dp[i - 1] * (11 - i);

      // 累加上 dp[i]（i位出现不同数字整数的总个数）
      sum += dp[i];
    }

    // 5.
    return sum;
  }
};